// 2025/11/8
// 螺旋矩阵

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<pair<int, int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        vector<int> bound = {-1, m, -1, n};
        vector<pair<int, int>> change = {{0, 1}, {3, -1}, {1, -1}, {2, 1}};
        int x = 0, y = 0, cur_dir = 0;
        vector<int> ans;
        while(bound[0] < x && x < bound[1] && bound[2] < y && y < bound[3])
        {
            ans.emplace_back(matrix[x][y]);
            int nx = x + dir[cur_dir].first, ny = y + dir[cur_dir].second;
            if(bound[0] < nx && nx < bound[1] && bound[2] < ny && ny < bound[3])
                x = nx, y = ny;
            else
            {
                bound[change[cur_dir].first] += change[cur_dir].second;
                cur_dir = (cur_dir + 1) % 4;
                x = x + dir[cur_dir].first;
                y = y + dir[cur_dir].second;
            }
        }
        return ans;
    }
};